# coding: utf-8
'''
Created on 21/06/2013

@author: Vagner Clementino
'''

from primeGen.miller_rabin import exp_mod_n
from quadraticSieve.trial_division import trial_division

def get_generator(P):
    '''
        Retornar o gerador, também conhecida como elemento primitivo
        de grupo multiplicativo módulo P, onde P é primo
    '''
    #Definindo o valor da função phi de Euler
    euler_phi_function = P-1 # por definição para valores primos
    
    #recuperando a lista de fatores primos de da funçaõ euler_phi    
    fatores_primos = trial_division(euler_phi_function)
    #númer de fatores primos da eulher_phi_function
    num_fatores = len(fatores_primos)
    #utilizado para verificar se foram realizados testes
    # com todos os os fatores primos de euler_phi_function
    testes_executados = 0
    a = long(2)
        
    while a < (P-1):
        for prime in fatores_primos:
            t = exp_mod_n(a,int(euler_phi_function/prime),P)
            if ( t  == 1):
                break
            else:
                testes_executados +=1
                                
        if (num_fatores == testes_executados):
                generator = a
                break
        else:
            testes_executados = 0
            a += 1
    return generator
                
